home *** CD-ROM | disk | FTP | other *** search
/ Nautilus 1992 July / Nautilus-3-8 / Nautilus-3-8.bin / Tools & Utilities / Techy Stuff / Source ƒ / egrep-1.5 / grep-src / glob.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-08-29  |  12.5 KB  |  563 lines
  1. /* Define GTEST to cause a test main program at the end of this
  2.    file to be compiled.  Remove it to call glob_filename from a
  3.    program with some other main.
  4. */
  5.  
  6. /* Note:  This code has been modfied to run on the
  7.    Macintosh under THINK C 5.0.  It is NOT the source as distributed
  8.    by the Free Software Foundation as part of bash.  Not even close.
  9. */
  10.  
  11. /* File-name wildcard pattern matching for GNU.
  12.    Copyright (C) 1985, 1988, 1989 Free Software Foundation, Inc.
  13.  
  14.    This program is free software; you can redistribute it and/or modify
  15.    it under the terms of the GNU General Public License as published by
  16.    the Free Software Foundation; either version 1, or (at your option)
  17.    any later version.
  18.  
  19.    This program is distributed in the hope that it will be useful,
  20.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  21.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22.    GNU General Public License for more details.
  23.  
  24.    You should have received a copy of the GNU General Public License
  25.    along with this program; if not, write to the Free Software
  26.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  27.  
  28. /* To whomever it may concern: I have never seen the code which most
  29.    Unix programs use to perform this function.  I wrote this from scratch
  30.    based on specifications for the pattern matching.  --RMS.  */
  31.  
  32.  
  33. #define D_NAMLEN(d) ((d)->d_namlen)
  34.  
  35. #include <stdio.h>
  36. #include <string.h>
  37. #include <stdlib.h>
  38. #include "common.h"
  39. #include "dirent.h"
  40.  
  41. #define bcopy(s,t,n) memmove(t,s,n)
  42. #define bcmp(b1,b2,n) memcmp(b1,b2,n)
  43. #define bzero(b,n) memset(b,0,n)
  44. extern void *alloca();
  45.  
  46. #ifndef NULL
  47. #define NULL 0
  48. #endif
  49.  
  50. /* Global variable which controls whether or not * matches .*.
  51.    Non-zero means don't match .*.  */
  52. int noglob_dot_filenames = 1;
  53.  
  54. /* Return nonzero if PATTERN has any special globbing chars in it.  */
  55. static int
  56. glob_pattern_p (pattern)
  57.      char *pattern;
  58. {
  59.   register char *p = pattern;
  60.   register char c;
  61.   int   open = 0;
  62.  
  63.   while ((c = *p++) != '\0')
  64.     switch (c)
  65.       {
  66.       case '?':
  67.       case '*':
  68.         return 1;
  69.  
  70.       case '[':         /* Only accept an open brace if there is a close */
  71.         open++;         /* brace to match it.  Bracket expressions must be */
  72.         continue;       /* complete, according to Posix.2 */
  73.       case ']':
  74.         if (open)
  75.           return 1;
  76.         continue;
  77.  
  78.       case '\\':
  79.         if (*p++ == '\0')
  80.           return 0;
  81.       }
  82.  
  83.   return 0;
  84. }
  85.  
  86. static int glob_match_after_star ();
  87.  
  88. /* Match the pattern PATTERN against the string TEXT;
  89.    return 1 if it matches, 0 otherwise.
  90.  
  91.    A match means the entire string TEXT is used up in matching.
  92.  
  93.    In the pattern string, `*' matches any sequence of characters,
  94.    `?' matches any character, [SET] matches any character in the specified set,
  95.    [!SET] matches any character not in the specified set.
  96.  
  97.    A set is composed of characters or ranges; a range looks like
  98.    character hyphen character (as in 0-9 or A-Z).
  99.    [0-9a-zA-Z_] is the set of characters allowed in C identifiers.
  100.    Any other character in the pattern must be matched exactly.
  101.  
  102.    To suppress the special syntactic significance of any of `[]*?!-\',
  103.    and match the character exactly, precede it with a `\'.
  104.  
  105.    If DOT_SPECIAL is nonzero,
  106.    `*' and `?' do not match `.' at the beginning of TEXT.  */
  107.  
  108. static int
  109. glob_match (pattern, text, dot_special)
  110.      char *pattern, *text;
  111.      int dot_special;
  112. {
  113.   register char *p = pattern, *t = text;
  114.   register char c;
  115.  
  116.   while ((c = *p++) != '\0')
  117.     switch (c)
  118.       {
  119.       case '?':
  120.     if (*t == '\0' || (dot_special && t == text && *t == '.'))
  121.       return 0;
  122.     else
  123.       ++t;
  124.     break;
  125.  
  126.       case '\\':
  127.     if (*p++ != *t++)
  128.       return 0;
  129.     break;
  130.  
  131.       case '*':
  132.     if (dot_special && t == text && *t == '.')
  133.       return 0;
  134.     return glob_match_after_star (p, t);
  135.  
  136.       case '[':
  137.     {
  138.       register char c1 = *t++;
  139.       int invert;
  140.  
  141.       if (!c1)
  142.         return (0);
  143.  
  144.       invert = ((*p == '!') || (*p == '^'));
  145.       if (invert)
  146.         p++;
  147.  
  148.       c = *p++;
  149.       while (1)
  150.         {
  151.           register char cstart = c, cend = c;
  152.  
  153.           if (c == '\\')
  154.         {
  155.           cstart = *p++;
  156.           cend = cstart;
  157.         }
  158.  
  159.           if (c == '\0')
  160.         return 0;
  161.  
  162.           c = *p++;
  163.           if (c == '-')
  164.         {
  165.           cend = *p++;
  166.           if (cend == '\\')
  167.             cend = *p++;
  168.           if (cend == '\0')
  169.             return 0;
  170.           c = *p++;
  171.         }
  172.           if (c1 >= cstart && c1 <= cend)
  173.         goto match;
  174.           if (c == ']')
  175.         break;
  176.         }
  177.       if (!invert)
  178.         return 0;
  179.       break;
  180.  
  181.     match:
  182.       /* Skip the rest of the [...] construct that already matched.  */
  183.       while (c != ']')
  184.         { 
  185.           if (c == '\0')
  186.         return 0;
  187.           c = *p++;
  188.           if (c == '\0')
  189.         return 0;
  190.           else if (c == '\\')
  191.         ++p;
  192.         }
  193.       if (invert)
  194.         return 0;
  195.       break;
  196.     }
  197.  
  198.       default:
  199.     if (c != *t++)
  200.       return 0;
  201.       }
  202.  
  203.   return *t == '\0';
  204. }
  205.  
  206. /* Like glob_match, but match PATTERN against any final segment of TEXT.  */
  207.  
  208. static int
  209. glob_match_after_star (pattern, text)
  210.      char *pattern, *text;
  211. {
  212.   register char *p = pattern, *t = text;
  213.   register char c, c1;
  214.  
  215.   while ((c = *p++) == '?' || c == '*')
  216.     if (c == '?' && *t++ == '\0')
  217.       return 0;
  218.  
  219.   if (c == '\0')
  220.     return 1;
  221.  
  222.   if (c == '\\')
  223.     c1 = *p;
  224.   else
  225.     c1 = c;
  226.  
  227.   while (1)
  228.     {
  229.       if ((c == '[' || *t == c1) && glob_match (p - 1, t, 0))
  230.     return 1;
  231.       if (*t++ == '\0')
  232.     return 0;
  233.     }
  234. }
  235.  
  236. /* Return a vector of names of files in the current directory.
  237.    The names are not in any particular order.
  238.    Wildcards at the beginning of PAT do not match an initial period.
  239.  
  240.    The vector is terminated by an element that is a null pointer.
  241.  
  242.    To free the space allocated, first free the vector's elements,
  243.    then free the vector.
  244.  
  245.    Return 0 if cannot get enough memory to hold the pointer
  246.    and the names.
  247.  
  248.    Return -1 if cannot access directory DIR.
  249.    Look in errno for more information.  */
  250.  
  251. char **
  252. glob_filename (pat)
  253.      char *pat;
  254. {
  255.   struct globval
  256.     {
  257.       struct globval *next;
  258.       char *name;
  259.     };
  260.  
  261.   DIR *d;
  262.   char *dir = ".";
  263.   register struct dirent *dp;
  264.   struct globval *lastlink;
  265.   register struct globval *nextlink;
  266.   register char *nextname;
  267.   unsigned int count;
  268.   int lose;
  269.   register char **name_vector;
  270.   register unsigned int i;
  271.  
  272.   d = opendir (dir);
  273.   if (d == NULL)
  274.     return (char **) -1;
  275.  
  276.   lastlink = 0;
  277.   count = 0;
  278.   lose = 0;
  279.  
  280.   /* Scan the directory, finding all names that match.
  281.      For each name that matches, allocate a struct globval
  282.      on the stack and store the name in it.
  283.      Chain those structs together; lastlink is the front of the chain.  */
  284.   while (1)
  285.     {
  286.       dp = readdir (d);
  287.       if (dp == NULL)
  288.     break;
  289.       if (dp->d_ino != 0
  290.       && glob_match (pat, dp->d_name, noglob_dot_filenames))
  291.     {
  292.       nextlink = (struct globval *) alloca ((long) sizeof (struct globval));
  293.       nextlink->next = lastlink;
  294.       nextname = (char *) malloc ((size_t)(D_NAMLEN(dp) + 1));
  295.       if (nextname == NULL)
  296.         {
  297.           lose = 1;
  298.           break;
  299.         }
  300.       lastlink = nextlink;
  301.       nextlink->name = nextname;
  302.       bcopy (dp->d_name, nextname, (size_t) (D_NAMLEN(dp) + 1));
  303.       ++count;
  304.     }
  305.     }
  306.   (void) closedir (d);
  307.  
  308.   if (!lose)
  309.     {
  310.       name_vector = (char **) malloc ((size_t)((count + 1)
  311.                                         * sizeof (char *)));
  312.       lose |= name_vector == NULL;
  313.     }
  314.  
  315.   /* Have we run out of memory?  */
  316.   if (lose)
  317.     {
  318.       /* Here free the strings we have got.  */
  319.       while (lastlink)
  320.     {
  321.       free (lastlink->name);
  322.       lastlink = lastlink->next;
  323.     }
  324.       return NULL;
  325.     }
  326.  
  327.   /* Copy the name pointers from the linked list into the vector.  */
  328.   for (i = 0; i < count; ++i)
  329.     {
  330.       name_vector[i] = lastlink->name;
  331.       lastlink = lastlink->next;
  332.     }
  333.  
  334.   name_vector[count] = NULL;
  335.   return name_vector;
  336. }
  337.  
  338.  
  339. static int compar(const void *s1, const void *s2)
  340.  
  341. {
  342.    return strcmp(*(char **) s1, *(char **)s2);
  343. }
  344.  
  345.  
  346. struct lnode;
  347.  
  348. struct lnode {
  349.    char **argv_block;
  350.    struct lnode *next;
  351. };
  352.  
  353. /* Accept the address of argc and argv and return a new vector and
  354.    count after filename globbing.  This implementation does NOT
  355.    recognize pathnames.  Thinks like "/" and ":" will be treated
  356.    as part of the filename.  Effectively, you glob only within the
  357.    current directory.  The files found are sorted.
  358. */
  359.  
  360. void glob_argv(argc, argv)
  361.    int *argc;
  362.    char ***argv;
  363. {
  364.    int i, j;
  365.    char **retval, **value;
  366.    int TotalFiles = 0, NumFiles;
  367.    struct lnode *tmp, *head=NULL, *cur;
  368.    
  369.    if (*argc < 2) return; /* Nothing to glob */
  370.    
  371.    for (i = 1; i < *argc; i++) { 
  372.       if (glob_pattern_p ((*argv)[i]))
  373.          value = glob_filename ((*argv)[i]);
  374.        else {        /* Do nothing to names with no magic chars */
  375.           value = (char **) malloc((size_t) 2*sizeof(char *));
  376.           value[0] = (*argv)[i];
  377.           value[1] = NULL;
  378.        }
  379.        
  380.       if (value == NULL) {
  381.          emitdata("%s\n", "Out of memory.");
  382.          exit(1);   
  383.       } else if ((int) value == -1)
  384.          emitdata("%s\n", *argv[i]);
  385.       else {
  386.          tmp = (struct lnode *) malloc((size_t) sizeof(struct lnode));
  387.          tmp->next = NULL;
  388.          tmp->argv_block = value;
  389.          NumFiles = 0;
  390.          for (j = 0; value[j] != NULL; j++) {
  391.             TotalFiles++;
  392.             NumFiles++;
  393.          }
  394.  
  395.          qsort((void *) value, (size_t) NumFiles, sizeof(char *),
  396.                compar);
  397.          /* append to list */
  398.          if (head == NULL) head =tmp;
  399.          else {
  400.             cur = head;
  401.             while (cur->next != NULL) cur = cur->next;
  402.             cur->next = tmp;
  403.          }   
  404.       }
  405.    } /* for */
  406.    
  407.    retval = (char **) malloc((size_t) (TotalFiles+1)*sizeof(char *));
  408.    cur = head;
  409.    retval[0] = (*argv)[0];
  410.    i = 1;
  411.    while (cur != NULL) {
  412.       j = 0;
  413.       while (cur->argv_block[j] != NULL) {
  414.          retval[i] = cur->argv_block[j];
  415.          i++;
  416.          j++;
  417.       }
  418.       tmp = cur;
  419.       cur = cur->next;
  420.       free(tmp->argv_block);
  421.       free(tmp);
  422.    }
  423.    
  424.    *argc = TotalFiles+1;
  425.    *argv = retval;
  426.   
  427. }
  428.  
  429. static short fini;
  430. static short curpos;
  431.  
  432. static char *findfile(flist)
  433.    char *flist;
  434. {
  435.    int endpos;
  436.    char *p;
  437.    
  438.    if (fini) return NULL;
  439.    
  440.    while (flist[curpos] == ' ' || flist[curpos] == '\t')
  441.       curpos++;  /* skip whitespace */
  442.       
  443.    endpos = curpos;
  444.    while (flist[endpos] != ' ' && flist[endpos] != '\t' &&
  445.           flist[endpos] != '\0') endpos++;  /* skip to white space */
  446.           
  447.    if (endpos == curpos) return NULL;
  448.    if (flist[endpos] == '\0') fini = 1;
  449.   
  450.    p = (char *) malloc((size_t) (endpos - curpos + 1));
  451.    memcpy(p, &(flist[curpos]), (size_t) (endpos - curpos));
  452.    p[endpos - curpos] = '\0';
  453.    
  454.    curpos = endpos + 1;
  455.    
  456.    return p;
  457. }
  458.  
  459.  
  460.  
  461. void glob_filelist(flist, argc, argv)
  462.    char *flist;
  463.    int *argc;
  464.    char ***argv;
  465. {
  466.    int i, j;
  467.    char **retval, **value;
  468.    char *file;
  469.    int TotalFiles = 0, NumFiles;
  470.    struct lnode *tmp, *head=NULL, *cur;
  471.    
  472.    fini = 0;
  473.    curpos = 0;
  474.    
  475.    while ((file = findfile(flist)) != NULL) {
  476.    
  477.       if (glob_pattern_p (file))
  478.          value = glob_filename (file);
  479.        else {        /* Do nothing to names with no magic chars */
  480.           value = (char **) malloc((size_t) 2*sizeof(char *));
  481.           value[0] = file;
  482.           value[1] = NULL;
  483.        }
  484.        
  485.       if (value == NULL) {
  486.          emitdata("%s\n", "Out of memory.");
  487.          exit(1);   
  488.       } else if ((int) value == -1)
  489.          emitdata("%s\n", *argv[i]);
  490.       else {
  491.          tmp = (struct lnode *) malloc((size_t) sizeof(struct lnode));
  492.          tmp->next = NULL;
  493.          tmp->argv_block = value;
  494.          NumFiles = 0;
  495.          for (j = 0; value[j] != NULL; j++) {
  496.             TotalFiles++;
  497.             NumFiles++;
  498.          }
  499.  
  500.          qsort((void *) value, (size_t) NumFiles, sizeof(char *),
  501.                compar);
  502.          /* append to list */
  503.          if (head == NULL) head =tmp;
  504.          else {
  505.             cur = head;
  506.             while (cur->next != NULL) cur = cur->next;
  507.             cur->next = tmp;
  508.          }   
  509.       }
  510.       
  511.    } /* while */
  512.    
  513.    retval = (char **) malloc((size_t) (TotalFiles)*sizeof(char *));
  514.    cur = head;
  515.    i = 0;
  516.    while (cur != NULL) {
  517.       j = 0;
  518.       while (cur->argv_block[j] != NULL) {
  519.          retval[i] = cur->argv_block[j];
  520.          i++;
  521.          j++;
  522.       }
  523.       tmp = cur;
  524.       cur = cur->next;
  525.       free(tmp->argv_block);
  526.       free(tmp);
  527.    }
  528.    
  529.    *argc = TotalFiles;
  530.    *argv = retval;
  531.   
  532. }
  533.  
  534. #ifdef GTEST
  535.  
  536. #include <console.h>
  537.  
  538. main (argc, argv)
  539.      int argc;
  540.      char **argv;
  541. {
  542.   unsigned int j;
  543.   
  544.   argc = ccommand(&argv);
  545.   glob_argv(&argc, &argv);
  546.  
  547.   for (j = 0; j < argc; j++)
  548.             printf ("%s\n", argv[j]);
  549.   exit (0);
  550. }
  551.  
  552. void *xmalloc(n)
  553.      size_t n;
  554. {
  555.   void *r = malloc(n);
  556.  
  557.   return r;
  558. }
  559.  
  560. #endif    /* TEST.  */
  561.  
  562.  
  563.